import java.util.*;

/**
 * Created by IntelliJ IDEA.
 *
 * @Author : Ding
 * @create 2022/4/15 21:45
 * <p>
 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
 * 算法的时间复杂度应该为 O(log (m+n)) 。
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums1 = [1,3], nums2 = [2]
 * 输出：2.00000
 * 解释：合并数组 = [1,2,3] ，中位数 2
 * 示例 2：
 * <p>
 * 输入：nums1 = [1,2], nums2 = [3,4]
 * 输出：2.50000
 * 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
 * <p>
 * 提示：
 * nums1.length == m
 * nums2.length == n
 * 0 <= m <= 1000
 * 0 <= n <= 1000
 * 1 <= m + n <= 2000
 * -106 <= nums1[i], nums2[i] <= 106
 */
public class _0004_寻找两个正序数组的中位数_困难 {
    public static void main(String[] args) {
        int[] nums1 = {1, 2};
        int[] nums2 = {3, 4};
        System.err.println(findMedianSortedArrays1(nums1, nums2));
    }


    /**
     * 二分查找法
     * 基本流程：先划出一个大概的分割线，然后利用二分查找不断接近那根正确的分割线
     * 时间、空间复杂度最小，代码可读性很差，可维护性很差 ./resource/0004.md
     * @param nums1 nums1
     * @param nums2 nums2
     * @return median
     */
    public static double findMedianSortedArrays1(int[] nums1, int[] nums2) {
        //首先，空杯子倒水法，令nums1长度最短
        if (nums1.length > nums2.length) {
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }

        int m = nums1.length;
        int n = nums2.length;
        //拟定一下，这两个小数组整体成为大数组的话，以中间划分，其左侧应该有多少个元素：(m + n +1) / 2
        //这样一来，就是向右取整，当偶数时，左右一样，当奇数时，左侧比右侧元素多一个
        int totalLeft = (m + n + 1) / 2;

        //以nums1为参照，为nums1规定边界，左边界初始为0，右边界初始为数组的长度m
        int left = 0;
        int right = m;

        //说了用二分法，那么就开始吧！
        while (left < right) {
            /*
                【为什么i是这个玩意？？】
                    因为i是[left,right]这样的区间的center，也就是说左边界不是固定位0的，
                    我们可以直到[left,right]这段区间的长度，right - left然后除以2就是它的中心，
                    但是对于下标来说，由于左边界不是0，所以还要加一个左边界的值，动态角标 = left角标 + [区间长度的一半]
                【那么为什么要写<right - left + 1>，这个“1”是啥意思】
                    这个要根据我们的判断逻辑来确定，一个理想的分界线，它划开两个数组的时候，必然满足如下条件：
                    nums1[i - 1] <= nums2[j] && nums2[i - 1] <= nums1[j]
                    所以我们取反的话，选择任意一个条件取反即可
                    当我们选择nums1[i-1] > nums2[j]时，是对右边界的缩小，当把分界线指向0，nums1[0-1]就会越界，且因为最大取nums1[m-1]，并不会向右越界，故向上取整
                    反之，选择nums2[i-1] > nums1[j]时，是对左边界的扩大，这个时候遵循程序默认的向下取整，就不会造成数组越界
             */
            int i = left + (right - left + 1) / 2;
            int j = totalLeft - i;
            if (nums1[i - 1] > nums2[j]) {
                right = i - 1;
            } else {
                //这为啥不是i+1？因为本身这里的i就没被取到<取的是i-1>，所以下一轮闭区间要带着这个i
                left = i;
            }
        }

        /*
            [1,3,4|]
            [2|,5,7,8]
            比如这是结果，那么影响结果的必然是2,4,5<4右边的取不到，防止越界我们有以下三元表达式铺垫>
         */
        int i = left;
        int j = totalLeft - i;
        int left1 = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
        int right1 = i == m ? Integer.MAX_VALUE : nums1[i];
        int left2 = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
        int right2 = j == n ? Integer.MAX_VALUE : nums2[j];

        if ((m + n) % 2 == 1) {
            //奇数，左侧最大值就是咯
            return Math.max(left1, left2);
        } else {
            //偶数，左侧最大值和右侧最小值的平均值
            return (Math.max(left1, left2) + Math.min(right1, right2)) / 2.0;
        }
    }


    /**
     * 我的解法（暴力解法）：Collections.sort排序法
     * 基本流程：合并为集合，然后使用java的api进行排序，最后直接输出
     * 代码可读性一般，复杂度较差运行时间很长（12ms）
     *
     * @param nums1 array1
     * @param nums2 array2
     * @return medianNum
     */
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        double ret = 0.0;
        //定义一个心集合
        List<Integer> list = new ArrayList<>();
        //将两个数组用一次循环添加到list集合
        for (int i = 0; i < Math.max(nums1.length, nums2.length); i++) {
            if (i < nums1.length) {
                list.add(nums1[i]);
            }
            if (i < nums2.length) {
                list.add(nums2[i]);
            }
        }
        //排序
        Collections.sort(list);
        //计算结果
        if (list.size() % 2 == 0) {
            //偶数
            int index1 = list.size() / 2 - 1;
            int index2 = index1 + 1;
            ret = (list.get(index1) + list.get(index2)) / 2.0;
        } else {
            //奇数
            ret = list.get(list.size() / 2) * 1.0;
        }
        return ret;
    }
}